package LCR;

public class detectCycle {
        public ListNode detectCycle(ListNode head) {
            if(head == null || head.next == null) return null; // 特判
            ListNode fast = head, slow = head;
            while(fast != null && fast.next != null){ // 注意两个条件的先后顺序（短路策略）
                fast = fast.next.next;
                slow = slow.next;
                if(slow == fast) break; // 快慢指针相遇
            }
            if(slow != fast) return null; // 无环时返回null，若能往下执行必有环
            fast = head; // 重复利用fast，放到表头处
            while(slow != fast){
                fast = fast.next;
                slow = slow.next;
            }
            return slow; // return fast也可以
        }

}
